public class test2 {
    class Solution {
        List<String> res;
        public List<String> generateParenthesis(int n) {
            res = new ArrayList<>();
            dfs("",n,n);
            return res;
        }
        private void dfs(String str,int left,int right){
            if(left==0 && right==0){
                res.add(str);
            }
            if(right<left){
                return;
            }
            if(left>0){
                dfs(str+"(",left-1,right);
            }
            if(right>0){
                dfs(str+")",left,right-1);
            }
        }
    }
}
